#include <stdio.h>
// #define NDEBUG
#include <assert.h>

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// void swap(SElemType *a,SElemType *b){
//     SElemType tmp = *a;
//     *a = *b;
//     *b = tmp;
// }

void insertion_sort(SElemType arr[], int len){
    SElemType choose;     // 可以认为是选中，要进行插入的牌
    int preIndex; // 选中的牌的前一个位置（开始进行插入的）
    int i; // 从第二张牌开始选
    for(i = 1; i < len; i++){
        choose = arr[i];
        preIndex = i-1;
        while(preIndex >= 0 && arr[preIndex] > choose){
            // 如果 arr[preIndex] > choose 大于被选中的牌就后移一位
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        // 跳出循环说明，已经找到比手牌还小的数, 插入其后面，且下标为preIndex
        arr[preIndex+1] = choose;
    }
}

int main(){
    SElemType arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    insertion_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
            printf("%d ", arr[i]);
    return 0;
}

